Umesh Vazirani
UC Berkeley
Abstract:
Quantum computation is entering an exciting new phase where quantum
thinking is becoming increasingly relevant to complexity theory. On the one hand, powerful quantum techniques have played an important role in
recent advances in questions about lattice cryptosystems, lower bounds for linear programs and the Lasserre hierarchy of semidefinite
programs. On the other, much as probabilistic thinking did starting in the early 80s,
quantum computing is expanding the core questions of complexity theory
in fundamental new directions. For example, here is a list of three basic questions
about quantum mechanics that are at their heart questions about computational complexity:
1. Do `typical' quantum states that occur in Nature have succinct (polynomial) description?
2. Can quantum systems at room temperature exhibit exponential complexity?
3. Is the scientific method sufficiently powerful to tackle general quantum systems?
Each of these issues is best studied through the computational lens as a question
about computation. The resulting questions lie at the core of computational complexity theory. The first asks about the structure of solutions to the quantum analog of SAT. The second asks
whether there is a quantum analog of the PCP theorem. And the third can be formulated as a question about interactive proof systems with quantum polynomial time provers. I will briefly
outline these connections and the state of the art on these questions.
The computational lens is a major theme for the new Simons Institute at Berkeley, and I will also briefly describe a special semester-long program on Quantum Hamiltonian Complexity that we are organizing at the Simons Institute in Spring 2014.